package com.cn.algorithm.two.greedy.test;

public class GreedyJ {

    public static void main(String[] args) {
        System.out.println(coins(41));
        System.out.println(coins2(41));
    }

    public static int coins(int n) {
        int[] arr = {25, 20, 5, 1};
        int index = 0;
        int count = 0;
        while (index < arr.length) {
            while (n >= arr[index]) {
                n -= arr[index];
                count++;
            }
            index++;
        }
        return count;
    }

    public static int coins2(int n) {
        if (n <= 0) {
            return Integer.MAX_VALUE;
        }
        if (n == 1 || n == 5 || n == 20 || n == 25) {
            return 1;
        }
        int min1 = Math.min(coins2(n - 1), coins2(n -5));
        int min2 = Math.min(coins2(n - 20), coins2(n -25));
        return Math.min(min1, min2) + 1;
    }
}
